package cg.studio.algorithm.array;

import org.junit.Test;

public class Swap
{
  @Test
  public void testGetMinSwaps()
  {
    {
      int[] arr1 = new int[]{ 0, 1 };
      int[] arr2 = new int[]{ 1, 0 };
      System.out.println( "suppose 1 : " + getMinSwaps(arr1, arr2) );
    }
    
    {
      int[] arr1 = new int[]{ 0, 0, 0, 1 };
      int[] arr2 = new int[]{ 1, 0, 0, 0 };
      System.out.println( "suppose 3 : " + getMinSwaps(arr1, arr2) );
    }
    
    {
      int[] arr1 = new int[]{ 0, 0, 0, 1 };
      int[] arr2 = new int[]{ 0, 1, 0, 0 };
      System.out.println( "suppose 2 : " + getMinSwaps(arr1, arr2) );
    }
    
    {
      int[] arr1 = new int[]{ 0, 1, 0, 0, 1, 0 };
      int[] arr2 = new int[]{ 1, 0, 0, 0, 0, 1 };
      System.out.println( "suppose 2 : " + getMinSwaps(arr1, arr2) );
    }
  }
  
  /**
   * Find minimum number of swaps to convert one binary array to another. 
    Note: It is always possible. 
    You are given two integer array having only 0's and 1's. Find minimum number of swaps to convert array1 to array2. 
    NOTE: You can only swap adjacent elements.
   *
   * solution:
   * compare the arrays and find number of 0/1 and divide array into sub-arrays, each sub-array meets following requirement.
   * - each sub-arrays have same 0/1 with destination sub-arrays
   * and convert each sub-arrays into destinations sub-arrays
   * the total minimum number of swaps equals sum of the number of each sub-arrays
   * 
   */
  
  /**
   * 
   * @param arr1 source array
   * @param arr2 destination array
   * @return
   */
  public static int getMinSwaps( int[] arr1, int[] arr2 )
  {
    if( arr1==null || arr2==null || arr1.length != arr2.length )
      throw new IllegalArgumentException( "Invalid input parameters." );
    
    //check number of 0/1
    int num11 = numberOf( arr1, 1 );
    int num10 = numberOf( arr1, 0 );
    if( num11 + num10 != arr1.length )
      throw new IllegalArgumentException( "There are number other than 0 and 1 in the array." );
    int num21 = numberOf( arr2, 1 );
    int num20 = numberOf( arr2, 0 );
    if( num21 + num20 != arr2.length )
      throw new IllegalArgumentException( "There are number other than 0 and 1 in the array." );
    if( num10 != num20 )
      throw new IllegalArgumentException( "arr1 can't swap to arr2 as there are different number of 0." );
    
    return getMinSwaps( arr1, arr2, 0, arr1.length-1 );
  }
  /**
   * change arr1 into arr2 by swap
   * @param arr1 source array
   * @param arr2 destination array
   * @param start start index, inclusive
   * @param end end index, inclusive
   * @return
   */
  public static int getMinSwaps( int[] arr1, int[] arr2, int start, int end )
  {
    int num11 = 0;
    int num21 = 0;
    boolean isSame = (arr1[start]==arr2[start]); //is array1 same as array2
    //if isSame, do aggressive untill isSame not true;
    if( isSame )
    {
      int i=start+1;
      for( ; i<=end && arr1[i]==arr2[i]; ++i ) ;
      if( i > end )
        return 0; //no swaps 
      
      //arr1[i] != arr2[i]
      return getMinSwaps( arr1, arr2, i, end );
    }
    
    //compare from end
    isSame = (arr1[end]==arr2[end]);
    if( isSame )
    {
      int i=end-1;
      for( ; i>=start && arr1[i]==arr2[i]; --i ) ;
      if( i < start )
        return 0; //no swaps 
      
      //arr1[i] != arr2[i]
      return getMinSwaps( arr1, arr2, start, i );
    }
        
    //not same, divide into to sub-arrays
    for( int i=start; i<=end; ++i )
    {
      if( arr1[i] == 1 )
        num11++;
      if( arr2[i] == 1 )
        num21++;
      
      if( num11 == num21 )
      {
        if( i != end )
          return getMinSwaps( arr1, arr2, start, i ) + getMinSwaps( arr1, arr2, i+1, end );
        else
        {
          //can't divide, have to swap
          //swap the number and swap to first. in fact, find first number which different from first number
          for( int j=start+1; j<=end; ++j )
          {
            if( arr1[j] != arr1[start] )
            {
              //find the item, swap directly, ( don't have to execute swap, only need to know how many swaps )
              arr1[ start ] = arr1[j];
              arr1[j] = (arr1[j] == 0 ? 1 : 0 );
              //swap (j-start) time in order to swap arr1[j] to arr1[start]
              return j-start + getMinSwaps( arr1, arr2, start+1, end );
            }
          }
        }
      }
      
    }
    
    //should not reach here
    throw new RuntimeException( "should not reach here." );
  }
  
  public static int numberOf( int[] arr, int value )
  {
    int count = 0;
    for( int v : arr )
    {
      if( v == value )
        count++;
    }
    return count;
  }
}
